﻿#region Copyright Notice
// 
// 
//  
//  Copyright (c) 2009-2011 Anindya Chatterjee
//  
//  Licensed under the Apache License, Version 2.0 (the "License");
//  you may not use this file except in compliance with the License.
//  You may obtain a copy of the License at
//  
//      http://www.apache.org/licenses/LICENSE-2.0
//  
//  Unless required by applicable law or agreed to in writing, software
//  distributed under the License is distributed on an "AS IS" BASIS,
//  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//  See the License for the specific language governing permissions and
//  limitations under the License.
// 
// 
#endregion
using System;
using System.Collections.Generic;

namespace AbstractClass.Collections.Generic
{
    /// <summary>
    /// Represents a self-balancing <see cref="BinarySearchTree&lt;T&gt;"/>, where 
    /// the heights of the two child sub-trees of any node differ by at most one.
    /// </summary>
    /// <typeparam name="T">The type of the data in the tree.</typeparam>
    /// <remarks>
    /// CREDIT : http://gopherproxy.org/sdf-eu.org/1/users/dasnar/res/
    /// </remarks>
    [Serializable]
    public class AVLTree<T> : BinarySearchTree<T>
    {
        /// <summary>
        /// Initializes a new instance of the <see cref="AVLTree&lt;T&gt;"/> class.
        /// </summary>
        public AVLTree()
        {
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="AVLTree&lt;T&gt;"/> class.
        /// </summary>
        /// <param name="collection">The collection of data.</param>
        public AVLTree(IEnumerable<T> collection)
            : base(collection)
        {
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="AVLTree&lt;T&gt;"/> class.
        /// </summary>
        /// <param name="comparer">The comparer to use to sort the data.</param>
        public AVLTree(Comparer<T> comparer)
            : base(comparer)
        {
        }

        /// <summary>
        ///   Adds an item to the <see cref="AVLTree&lt;T&gt;"/>.
        /// </summary>
        /// <param name = "value">The object to add to the <see cref="AVLTree&lt;T&gt;"/>.
        /// </param>
        public override void Add(T value)
        {
            if (Root == null)
            {
                Root = new BinaryTreeNode<T>(value);
            }
            else
            {
                BinaryTreeNode<T> root = Root;
                InsertNode(ref root, value);
                Root = root;
            }
            Count++;
        }

        /// <summary>
        ///   Removes the first occurrence of a specific object from the <see cref="AVLTree&lt;T&gt;"/>.
        /// </summary>
        /// <param name = "item">The object to remove from the <see cref="AVLTree&lt;T&gt;"/>.
        /// </param>
        /// <returns>
        ///   true if <paramref name = "item" /> was successfully removed from the <see cref="AVLTree&lt;T&gt;"/>;
        /// 		otherwise, false. This method also returns false if <paramref name = "item" /> is not found in the original
        /// 		<see cref="AVLTree&lt;T&gt;"/>.
        /// </returns>
        public override bool Remove(T item)
        {
            try
            {
                Root = RemoveNode(Root, item);
                Count--;
                return true;
            }
            catch (Exception)
            {
                return false;
            }
        }


        private static int Height(BinaryTreeNode<T> node)
        {
            return node == null ? 0 : node.Depth;
        }

        private static int GetBalanceFactor(BinaryTreeNode<T> node)
        {
            return node == null ? 0 : Height(node._Left) - Height(node._Right);
        }

        private void InsertNode(ref BinaryTreeNode<T> avlNode, T value)
        {
            BinaryTreeNode<T> left = avlNode._Left;
            BinaryTreeNode<T> right = avlNode._Right;

            if (Comparer.Compare(value, avlNode.Value) < 0)
            {
                if (avlNode._Left == null)
                {
                    avlNode._Left = new BinaryTreeNode<T>(value);
                }
                else
                {
                    InsertNode(ref left, value);
                    avlNode._Left = left;
                }
            }
            else if (Comparer.Compare(value, avlNode.Value) > 0)
            {
                if (avlNode._Right == null)
                {
                    avlNode._Right = new BinaryTreeNode<T>(value);
                }
                else
                {
                    InsertNode(ref right, value);
                    avlNode._Right = right;
                }
            }
            if ((GetBalanceFactor(avlNode) == 2) || (GetBalanceFactor(avlNode) == -2))
            {
                Balance(ref avlNode);
            }
            else
            {
                AdjustHeight(avlNode);
            }
        }

        private static void AdjustHeight(BinaryTreeNode<T> avlNode)
        {
            avlNode.Depth = Math.Max(Height(avlNode._Left), Height(avlNode._Right)) + 1;
        }

        private static void Balance(ref BinaryTreeNode<T> node)
        {
            if (GetBalanceFactor(node) == 2)
            {
                if (GetBalanceFactor(node._Left) > -1)
                {
                    SingleRightRotation(ref node);
                }
                else
                {
                    DoubleLeftRightRotation(ref node);
                }
            }
            else if (GetBalanceFactor(node) == -2)
            {
                if (GetBalanceFactor(node._Right) < 1)
                {
                    SingleLeftRotation(ref node);
                }
                else
                {
                    DoubleRightLeftRotation(ref node);
                }
            }
        }

        private BinaryTreeNode<T> RemoveNode(BinaryTreeNode<T> avlNode, T item)
        {
            if (avlNode == null)
            {
                throw new Exception("item not found");
            }
            if (Comparer.Compare(item, avlNode.Value) < 0)
            {
                avlNode._Left = RemoveNode(avlNode._Left, item);
            }
            else if (Comparer.Compare(item, avlNode.Value) > 0)
            {
                avlNode._Right = RemoveNode(avlNode._Right, item);
            }
            else if (Comparer.Compare(item, avlNode.Value) == 0)
            {
                if (avlNode._Right == null && avlNode._Left == null)
                {
                    return null;
                }
                if (avlNode._Right != null && avlNode._Left == null)
                {
                    return avlNode._Right;
                }
                if (avlNode._Right == null)
                {
                    return avlNode._Left;
                }
                T newValue = FindMaxValue(avlNode._Left);
                avlNode.Value = newValue;
                avlNode._Left = RemoveNode(avlNode._Left, newValue);
            }
            if ((GetBalanceFactor(avlNode) == 2) || (GetBalanceFactor(avlNode) == -2))
            {
                Balance(ref avlNode);
            }
            else
            {
                AdjustHeight(avlNode);
            }

            return avlNode;
        }

        private static T FindMaxValue(BinaryTreeNode<T> avlTreeNode)
        {
            while (avlTreeNode._Right != null)
            {
                avlTreeNode = avlTreeNode._Right;
            }

            T max = avlTreeNode.Value;
            return max;
        }

        private static void DoubleLeftRightRotation(ref BinaryTreeNode<T> node)
        {
            BinaryTreeNode<T> node1 = node._Left._Right;
            node._Left._Right = node1._Left;
            node1._Left = node._Left;
            AdjustHeight(node._Left);
            AdjustHeight(node);

            node._Left = node1._Right;
            node1._Right = node;
            AdjustHeight(node);
            AdjustHeight(node1);
            node = node1;
        }

        private static void SingleLeftRotation(ref BinaryTreeNode<T> node)
        {
            BinaryTreeNode<T> node1 = node._Right;
            node._Right = node1._Left;
            node1._Left = node;
            AdjustHeight(node);
            AdjustHeight(node1);
            node = node1;
        }

        private static void DoubleRightLeftRotation(ref BinaryTreeNode<T> node)
        {
            BinaryTreeNode<T> node1 = node._Right._Left;
            node._Right._Left = node1._Right;
            node1._Right = node._Right;
            AdjustHeight(node._Right);
            AdjustHeight(node1);

            node._Right = node1._Left;
            node1._Left = node;
            AdjustHeight(node);
            AdjustHeight(node1);
            node = node1;
        }

        private static void SingleRightRotation(ref BinaryTreeNode<T> node)
        {
            BinaryTreeNode<T> node1 = node._Left;
            node._Left = node1._Right;
            node1._Right = node;
            AdjustHeight(node);
            AdjustHeight(node1);
            node = node1;
        }
    }

    #region Obsolete Code

    //public override void Add(T value)
    //    {
    //        var node = new BinaryTreeNode<T>(value);

    //        var current = Root;
    //        if (current == null)
    //        {
    //            Root = node;
    //        }
    //        else
    //        {
    //            while (true)
    //            {
    //                var result = Comparer.Compare(node.Value, current.Value);

    //                if (result < 0)
    //                {
    //                    if (current.Left != null)
    //                    {
    //                        current = current.Left;
    //                    }
    //                    else
    //                    {
    //                        current.Left = node;
    //                        current.Balance--;

    //                        break;
    //                    }
    //                }
    //                else if (result > 0)
    //                {
    //                    if (current.Right != null)
    //                    {
    //                        current = current.Right;
    //                    }
    //                    else
    //                    {
    //                        current.Right = node;
    //                        current.Balance++;

    //                        break;
    //                    }
    //                }
    //                else
    //                    return;
    //            }

    //            while ((current.Balance != 0) && (current.Parent != null))
    //            {
    //                if (((BinaryTreeNode<T>) current.Parent).Left == current)
    //                {
    //                    ((BinaryTreeNode<T>) current.Parent).Balance--;
    //                }
    //                else
    //                {
    //                    ((BinaryTreeNode<T>) current.Parent).Balance++;
    //                }

    //                current = current.Parent as BinaryTreeNode<T>;

    //                switch (current.Balance)
    //                {
    //                    case -2:
    //                        {
    //                            var left = current.Left;

    //                            if (left.Balance == -1)
    //                            {
    //                                left.Parent = current.Parent;

    //                                if (current.Parent == null)
    //                                {
    //                                    Root = left;
    //                                }
    //                                else
    //                                {
    //                                    if (((BinaryTreeNode<T>) current.Parent).Left == current)
    //                                    {
    //                                        ((BinaryTreeNode<T>) current.Parent).Left = left;
    //                                    }
    //                                    else
    //                                    {
    //                                        ((BinaryTreeNode<T>) current.Parent).Right = left;
    //                                    }
    //                                }

    //                                current.Left = left.Right;

    //                                if (current.Left != null)
    //                                {
    //                                    current.Left.Parent = current;
    //                                }

    //                                left.Right = current;
    //                                current.Parent = left;

    //                                left.Balance = 0;
    //                                current.Balance = 0;
    //                            }
    //                            else
    //                            {
    //                                var right = left.Right;

    //                                right.Parent = current.Parent;

    //                                if (current.Parent == null)
    //                                {
    //                                    Root = right;
    //                                }
    //                                else
    //                                {
    //                                    if (((BinaryTreeNode<T>) current.Parent).Left == current)
    //                                    {
    //                                        ((BinaryTreeNode<T>) current.Parent).Left = right;
    //                                    }
    //                                    else
    //                                    {
    //                                        ((BinaryTreeNode<T>) current.Parent).Right = right;
    //                                    }
    //                                }

    //                                left.Right = right.Left;

    //                                if (left.Right != null)
    //                                {
    //                                    left.Right.Parent = left;
    //                                }

    //                                current.Left = right.Right;

    //                                if (current.Left != null)
    //                                {
    //                                    current.Left.Parent = current;
    //                                }

    //                                right.Left = left;
    //                                right.Right = current;

    //                                left.Parent = right;
    //                                current.Parent = right;

    //                                switch (right.Balance)
    //                                {
    //                                    case -1:
    //                                        left.Balance = 0;
    //                                        current.Balance = 1;
    //                                        break;
    //                                    case 0:
    //                                        left.Balance = 0;
    //                                        current.Balance = 0;
    //                                        break;
    //                                    default:
    //                                        left.Balance = -1;
    //                                        current.Balance = 0;
    //                                        break;
    //                                }

    //                                right.Balance = 0;
    //                            }

    //                            break;
    //                        }
    //                    case 2:
    //                        {
    //                            var right = current.Right;

    //                            if (right.Balance == 1)
    //                            {
    //                                right.Parent = current.Parent;

    //                                if (current.Parent == null)
    //                                {
    //                                    Root = right;
    //                                }
    //                                else
    //                                {
    //                                    if (((BinaryTreeNode<T>) current.Parent).Left == current)
    //                                    {
    //                                        ((BinaryTreeNode<T>) current.Parent).Left = right;
    //                                    }
    //                                    else
    //                                    {
    //                                        ((BinaryTreeNode<T>) current.Parent).Right = right;
    //                                    }
    //                                }

    //                                current.Right = right.Left;

    //                                if (current.Right != null)
    //                                {
    //                                    current.Right.Parent = current;
    //                                }

    //                                right.Left = current;
    //                                current.Parent = right;

    //                                right.Balance = 0;
    //                                current.Balance = 0;
    //                            }
    //                            else
    //                            {
    //                                var left = right.Left;


    //                                #region Debug

    //                                if(left == null)
    //                                {
    //                                    Console.WriteLine(right);
    //                                    Console.WriteLine(right.Parent);
    //                                    Console.WriteLine(right.Right);
    //                                    Console.WriteLine(Count);
    //                                }

    //                                #endregion

    //                                left.Parent = current.Parent;

    //                                if (current.Parent == null)
    //                                {
    //                                    Root = left;
    //                                }
    //                                else
    //                                {
    //                                    if (((BinaryTreeNode<T>) current.Parent).Left == current)
    //                                    {
    //                                        ((BinaryTreeNode<T>) current.Parent).Left = left;
    //                                    }
    //                                    else
    //                                    {
    //                                        ((BinaryTreeNode<T>) current.Parent).Right = left;
    //                                    }
    //                                }

    //                                right.Left = left.Right;

    //                                if (right.Left != null)
    //                                {
    //                                    right.Left.Parent = right;
    //                                }

    //                                current.Right = left.Left;

    //                                if (current.Right != null)
    //                                {
    //                                    current.Right.Parent = current;
    //                                }

    //                                left.Right = right;
    //                                left.Left = current;

    //                                right.Parent = left;
    //                                current.Parent = left;

    //                                switch (left.Balance)
    //                                {
    //                                    case 1:
    //                                        right.Balance = 0;
    //                                        current.Balance = -1;
    //                                        break;
    //                                    case 0:
    //                                        right.Balance = 0;
    //                                        current.Balance = 0;
    //                                        break;
    //                                    default:
    //                                        right.Balance = 1;
    //                                        current.Balance = 0;
    //                                        break;
    //                                }

    //                                left.Balance = 0;
    //                            }

    //                            break;
    //                        }
    //                }
    //            }
    //        }
    //        Count++;
    //    }


    //public override bool Remove(T item)
    //    {
    //        var parent = Root;

    //        while (parent != null)
    //        {
    //            var result = Comparer.Compare(item, parent.Value);

    //            if (result < 0)
    //            {
    //                parent = parent.Left;
    //            }
    //            else if (result > 0)
    //            {
    //                parent = parent.Right;
    //            }
    //            else
    //            {
    //                BinaryTreeNode<T> current;

    //                if (parent.Right == null)
    //                {
    //                    if (parent.Left != null)
    //                    {
    //                        parent.Left.Parent = parent.Parent;
    //                    }

    //                    if (parent.Parent == null)
    //                    {
    //                        Root = parent.Left;

    //                        goto Done;
    //                    }

    //                    if (parent == ((BinaryTreeNode<T>) parent.Parent).Left)
    //                    {
    //                        ((BinaryTreeNode<T>) parent.Parent).Left = parent.Left;

    //                        current = (BinaryTreeNode<T>) parent.Parent;
    //                    }
    //                    else
    //                    {
    //                        ((BinaryTreeNode<T>) parent.Parent).Right = parent.Left;

    //                        current = (BinaryTreeNode<T>) parent.Parent;
    //                        goto RightDelete;
    //                    }
    //                }
    //                else if (parent.Right.Left == null)
    //                {
    //                    if (parent.Left != null)
    //                    {
    //                        parent.Left.Parent = parent.Right;
    //                        parent.Right.Left = parent.Left;
    //                    }

    //                    parent.Right.Balance = parent.Balance;
    //                    parent.Right.Parent = parent.Parent;

    //                    if (parent.Parent == null)
    //                    {
    //                        Root = parent.Right;
    //                    }
    //                    else
    //                    {
    //                        if (parent == ((BinaryTreeNode<T>) parent.Parent).Left)
    //                        {
    //                            ((BinaryTreeNode<T>) parent.Parent).Left = parent.Right;
    //                        }
    //                        else
    //                        {
    //                            ((BinaryTreeNode<T>) parent.Parent).Right = parent.Right;
    //                        }
    //                    }

    //                    current = parent.Right;

    //                    goto RightDelete;
    //                }
    //                else
    //                {
    //                    var left = parent.Right.Left;

    //                    while (left.Left != null)
    //                    {
    //                        left = left.Left;
    //                    }

    //                    if (parent.Left != null)
    //                    {
    //                        parent.Left.Parent = left;
    //                        left.Left = parent.Left;
    //                    }

    //                    ((BinaryTreeNode<T>) left.Parent).Left = left.Right;

    //                    if (left.Right != null)
    //                    {
    //                        left.Right.Parent = left.Parent;
    //                    }

    //                    parent.Right.Parent = left;
    //                    left.Right = parent.Right;

    //                    current = (BinaryTreeNode<T>) left.Parent;

    //                    left.Balance = parent.Balance;
    //                    left.Parent = parent.Parent;

    //                    if (parent.Parent == null)
    //                    {
    //                        Root = left;
    //                    }
    //                    else
    //                    {
    //                        if (parent == ((BinaryTreeNode<T>) parent.Parent).Left)
    //                        {
    //                            ((BinaryTreeNode<T>) parent.Parent).Left = left;
    //                        }
    //                        else
    //                        {
    //                            ((BinaryTreeNode<T>) parent.Parent).Right = left;
    //                        }
    //                    }
    //                }

    //                LeftDelete:

    //                current.Balance++;

    //                switch (current.Balance)
    //                {
    //                    case 1:
    //                        goto Done;
    //                    case 2:
    //                        {
    //                            var right = current.Right;

    //                            if (right.Balance == -1)
    //                            {
    //                                var left = right.Left;

    //                                left.Parent = current.Parent;

    //                                if (current.Parent == null)
    //                                {
    //                                    Root = left;
    //                                }
    //                                else
    //                                {
    //                                    if (((BinaryTreeNode<T>) current.Parent).Left == current)
    //                                    {
    //                                        ((BinaryTreeNode<T>) current.Parent).Left = left;
    //                                    }
    //                                    else
    //                                    {
    //                                        ((BinaryTreeNode<T>) current.Parent).Right = left;
    //                                    }
    //                                }

    //                                right.Left = left.Right;

    //                                if (right.Left != null)
    //                                {
    //                                    right.Left.Parent = right;
    //                                }

    //                                current.Right = left.Left;

    //                                if (current.Right != null)
    //                                {
    //                                    current.Right.Parent = current;
    //                                }

    //                                left.Right = right;
    //                                left.Left = current;

    //                                right.Parent = left;
    //                                current.Parent = left;

    //                                switch (left.Balance)
    //                                {
    //                                    case 1:
    //                                        right.Balance = 0;
    //                                        current.Balance = -1;
    //                                        break;
    //                                    case 0:
    //                                        right.Balance = 0;
    //                                        current.Balance = 0;
    //                                        break;
    //                                    default:
    //                                        right.Balance = 1;
    //                                        current.Balance = 0;
    //                                        break;
    //                                }

    //                                left.Balance = 0;

    //                                current = left;
    //                            }
    //                            else
    //                            {
    //                                right.Parent = current.Parent;

    //                                if (current.Parent != null)
    //                                {
    //                                    if (((BinaryTreeNode<T>) current.Parent).Left == current)
    //                                    {
    //                                        ((BinaryTreeNode<T>) current.Parent).Left = right;
    //                                    }
    //                                    else
    //                                    {
    //                                        ((BinaryTreeNode<T>) current.Parent).Right = right;
    //                                    }
    //                                }
    //                                else
    //                                {
    //                                    Root = right;
    //                                }

    //                                current.Right = right.Left;

    //                                if (current.Right != null)
    //                                {
    //                                    current.Right.Parent = current;
    //                                }

    //                                right.Left = current;
    //                                current.Parent = right;

    //                                if (right.Balance == 0)
    //                                {
    //                                    right.Balance = -1;
    //                                    current.Balance = 1;

    //                                    goto Done;
    //                                }
    //                                right.Balance = 0;
    //                                current.Balance = 0;

    //                                current = right;
    //                            }
    //                        }
    //                        break;
    //                }

    //                goto LoopTest;


    //                RightDelete:

    //                current.Balance--;

    //                switch (current.Balance)
    //                {
    //                    case -1:
    //                        goto Done;
    //                    case -2:
    //                        {
    //                            var left = current.Left;

    //                            if (left.Balance == 1)
    //                            {
    //                                var right = left.Right;

    //                                right.Parent = current.Parent;

    //                                if (current.Parent == null)
    //                                {
    //                                    Root = right;
    //                                }
    //                                else
    //                                {
    //                                    if (((BinaryTreeNode<T>) current.Parent).Left == current)
    //                                    {
    //                                        ((BinaryTreeNode<T>) current.Parent).Left = right;
    //                                    }
    //                                    else
    //                                    {
    //                                        ((BinaryTreeNode<T>) current.Parent).Right = right;
    //                                    }
    //                                }

    //                                left.Right = right.Left;

    //                                if (left.Right != null)
    //                                {
    //                                    left.Right.Parent = left;
    //                                }

    //                                current.Left = right.Right;

    //                                if (current.Left != null)
    //                                {
    //                                    current.Left.Parent = current;
    //                                }

    //                                right.Left = left;
    //                                right.Right = current;

    //                                left.Parent = right;
    //                                current.Parent = right;

    //                                switch (right.Balance)
    //                                {
    //                                    case -1:
    //                                        left.Balance = 0;
    //                                        current.Balance = 1;
    //                                        break;
    //                                    case 0:
    //                                        left.Balance = 0;
    //                                        current.Balance = 0;
    //                                        break;
    //                                    default:
    //                                        left.Balance = -1;
    //                                        current.Balance = 0;
    //                                        break;
    //                                }

    //                                right.Balance = 0;

    //                                current = right;
    //                            }
    //                            else
    //                            {
    //                                left.Parent = current.Parent;

    //                                if (current.Parent != null)
    //                                {
    //                                    if (((BinaryTreeNode<T>) current.Parent).Left == current)
    //                                    {
    //                                        ((BinaryTreeNode<T>) current.Parent).Left = left;
    //                                    }
    //                                    else
    //                                    {
    //                                        ((BinaryTreeNode<T>) current.Parent).Right = left;
    //                                    }
    //                                }
    //                                else
    //                                {
    //                                    Root = left;
    //                                }

    //                                current.Left = left.Right;

    //                                if (current.Left != null)
    //                                {
    //                                    current.Left.Parent = current;
    //                                }

    //                                left.Right = current;
    //                                current.Parent = left;

    //                                if (left.Balance == 0)
    //                                {
    //                                    left.Balance = 1;
    //                                    current.Balance = -1;

    //                                    goto Done;
    //                                }
    //                                left.Balance = 0;
    //                                current.Balance = 0;

    //                                current = left;
    //                            }
    //                        }
    //                        break;
    //                }

    //                LoopTest:

    //                if (current.Parent != null)
    //                {
    //                    if (current == ((BinaryTreeNode<T>) current.Parent).Left)
    //                    {
    //                        current = (BinaryTreeNode<T>) current.Parent;
    //                        goto LeftDelete;
    //                    }

    //                    current = (BinaryTreeNode<T>) current.Parent;
    //                    goto RightDelete;
    //                }

    //                Done:

    //                Count--;
    //                return true;
    //            }
    //        }
    //        return false;
    //    }

    #endregion
}